//
// Created by 高森森 on 2022/2/14.
//

#ifndef LEETCODE_SOLUTION44_H
#define LEETCODE_SOLUTION44_H

#include <iostream>
using namespace std;
#include<vector>
#include <numeric>
#include <algorithm>

class UnionFind4{
public:
    vector<int>father;//父亲节点
    vector<int>rank;//秩的数
    int n;//节点个数
    int setCount;//连通分量数
public:
    //查询父结点
    UnionFind4(int _n):n(_n),setCount(_n),rank(_n,1),father(_n){
        //iota函数，令father[i]=i;
        iota(father.begin(),father.end(),0);
    }
    int find(int x,vector<int>&father){
        if(x==father[x])
            return x;
        else{
            father[x]=find(father[x],father);
            return father[x];
        }
    }

    //并查集合并
    bool merge(int i,int j){
        int x=find(i,father);
        int y=find(j,father);
        if(x==y){
            return false;
        }
        if(rank[x]<=rank[y]){
            father[x]=y;
        }
        else{
            father[y]=x;
        }
        if(rank[x]==rank[y]&&x!=y)
            rank[y]++;
        setCount--;
        return true;
    }
    bool isConnected(int x,int y){
        x=find(x,father);
        y=find(y,father);
        return x==y;
    }
};

class Solution44 {
public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
        //kruskal计算最小生成树权值
        int m=edges.size();
        for(int i=0;i<m;i++){
            edges[i].push_back(i);
        }
        sort(edges.begin(),edges.end(),[](const vector<int>&a,const vector<int>&b){
            return a[2]<b[2];
        });
        UnionFind4 unionFind4(n);
        //计算最小生成树权值
        int value=0;
        for(int i=0;i<m;i++){
            if(unionFind4.merge(edges[i][0],edges[i][1])){
                value+=edges[i][2];
            }
        }
        vector<vector<int>>ans(2);
        //判断是否为关键边，就是如果关键边不加入并查集中合并，最小生成树的权值发生变化
        //就是关键边
        //如果是关键边，那么一定不是非关键边，跳过
        //如果不是关键边，那么重新创建一个并查集，这个并查集首先将这条边合并，
        // 如果最后的权值不变，说明是伪关键边

        //循环遍历m次，每次删除一条边验证是否关键边
        for(int i=0;i<m;i++)
        {
           UnionFind4 u1(n);
           int v=0;
           for(int j=0;j<m;j++){
               if(i!=j&&u1.merge(edges[j][0],edges[j][1]))
                   v+=edges[j][2];
           }
           if(u1.setCount!=1||(u1.setCount==1&&v>value)){
               ans[0].push_back(edges[i][3]);
               continue;//关键边一定不是伪关键边，所以直接跳过伪关键边的判断
           }

           UnionFind4 u2(n);
           u2.merge(edges[i][0],edges[i][1]);
           v=edges[i][2];
           for(int j=0;j<m;j++){
               if(j!=i&&u2.merge(edges[j][0],edges[j][1])){
                   v+=edges[j][2];
               }
           }
           if(v==value){
               ans[1].push_back(edges[i][3]);
           }
        }
        return ans;
    }
};


#endif //LEETCODE_SOLUTION44_H
